package com.example.demo.zaqizabatest.leetcode.day7;

/**
 * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 *
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 */
@SuppressWarnings("AlibabaLowerCamelCaseVariableNaming")
public class Solution1 {

    /**
     * 别人写的
     *
     * @param A
     * @param B
     * @return
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) {
            return false;
        }
        return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);



    }

    public boolean dfs(TreeNode A, TreeNode B){
        if(B == null) {
            return true;
        }
        if(A == null) {
            return false;
        }
        return A.val == B.val && dfs(A.left, B.left) && dfs(A.right, B.right);
    }
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /*private List<TreeNode> traversalA(List<TreeNode> tree, int BVal, TreeNode... subNodes) {
        List<TreeNode> subSubNodes = new ArrayList<>();
        if (subNodes.length != 0){
            for (TreeNode subNode : subNodes){
                if (BVal == subNode.val)
                    tree.add(subNode);
                if (subNode.left != null) {
                    subSubNodes.add(subNode.left);
                }
                if (subNode.right != null) {
                    subSubNodes.add(subNode.right);
                }
            }
            traversalA(tree, BVal, subSubNodes.toArray(new TreeNode[subSubNodes.size()]));
        }
        return tree;
    }

    private void traversal(List<Integer> tree, TreeNode... subNodes) {
        List<TreeNode> subSubNodes = new ArrayList<>();
        if (subNodes.length != 0){
            for (TreeNode subNode : subNodes){
                tree.add(subNode.val);
                if (subNode.left != null) {
                    subSubNodes.add(subNode.left);
                }
                if (subNode.right != null) {
                    subSubNodes.add(subNode.right);
                }
            }
            traversal(tree, subSubNodes.toArray(new TreeNode[subSubNodes.size()]));
        }
    }




    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        TreeNode root = new TreeNode(1);
        TreeNode root2 = new TreeNode(2);
        TreeNode root3 = new TreeNode(3);
        TreeNode root4 = new TreeNode(4);
        TreeNode rootB = new TreeNode(3);
        root.left = root2;
        root.right = root3;
        root2.left = root4;
        System.out.println(solution1.isSubStructure(root, rootB));
    }*/
}
